class Solution {
public:
    long long validSubstringCount(string s, string t) {
        // 这道题是昨天那道的进阶版，但是AC不了，需要进一步优化为O(n)
        if(s.size() < t.size()) 
            return 0;
        int hash1[26] = { 0 }, hash2[26] = { 0 };
        for(char &ch : t)
            hash2[ch - 'a']++;
        int n = s.size(), left = 0;
        long long ans = 0;
        // auto cmp = [&](int hash1[26], int hash2[26])->bool
        // {
        //     for(int i = 0; i < 26; i++)
        //         if(hash1[i] < hash2[i])
        //             return false;
        //     return true;
        // };
        // 时间复杂度是 O(26 * n)
        int cnt = 0, tSize = t.size();
        for(int i = 0; i < n; i++)
        {
            // 入窗口，有效字符，cnt++
            if(hash1[s[i] - 'a']++ < hash2[s[i] - 'a'])
                cnt++;

            // 找到使窗口最小且满足窗口内字符的出现个数都 >= hash2
            // 如果while循环结束，那么left的位置是刚刚好不满足窗口内字符的出现个数都 >= hash2
            // 所以left - 1是刚好满足，因此 0, 1, 2, ..., left - 1, 都是包含字符串t中所有字符的
            while(cnt >= tSize)     // 此处优化O(1)的判断，不用判断整个哈希表
            {
                if(--hash1[s[left] - 'a'] < hash2[s[left] - 'a'])   // 有效字符出窗口，cnt--
                    cnt--;
                left++;
            }
            ans += left;    // 0 到 left - 1，那么一共是 left 个
        }
        return ans;
    }
};